package com.example.algorithmdemo.slt;

import kotlin.jvm.internal.FunInterfaceConstructorReference;

/**
 * 链表
 */
public class STLNode {
    private static final String TAG = "STLNode";
    private STLNode next = null;
    private int value;
    private STLNode(int value){
        this.value = value;
    }

    public static void testSingleLinkTable(){

        STLNode first = new STLNode(1);
        first.next = null;
        STLNode second = new STLNode(2);
        first.next = second;
        second.next = null;
        STLNode third = new STLNode(3);
        second.next = third;
        third.next = null;
        printSTL(first);
    }

    /**
     * 链表的插入操作：新增哨兵节点，不必讨论链表换头操作
     * @param head
     * @param k 在k后插入.k为链表合法值
     * @param value
     * @return
     */
    STLNode insertNode(STLNode head,int k,int value){
        STLNode dummyNode = new STLNode(-1);
        dummyNode.next = head;
        STLNode cur = dummyNode;
        int count = 0;
        STLNode insertNode = new STLNode(value);
        while (cur != null){
            //在k个位置之前插入
//            if (k - 1 == count){
//                insertNode.next = cur.next;
//                cur.next = insertNode;
//            }
            cur = cur.next;
            count += 1;
            //在k个位置之后插入
            if (k == count){
                insertNode.next = cur.next;
                cur.next = insertNode;
            }
        }
        return dummyNode.next;
    }

    /**
     * 删除单链表中的元素
     * @param head
     * @param k
     * @return
     */
    STLNode deleteNode(STLNode head,int k){
        STLNode dummyNode = new STLNode(-1);
        dummyNode.next = head;
        STLNode cur = dummyNode;
        int count = 0;
        while (cur.next != null){
            cur = cur.next;
            count += 1;
            if (count == k -1){
                STLNode temp = cur.next;
                cur.next = cur.next.next;
                temp = null;
            }
        }
        return dummyNode;
    }

    /**
     * 单链表k个一组进行反转
     * @param start
     * @param end
     * @return
     */
    STLNode reverseKNode(STLNode start,STLNode end){
        STLNode pre = start;
        STLNode cur = start.next;
        STLNode first = cur;
        while (cur!=end){
            STLNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        start.next = pre;//头
        first.next = end;//尾部链接下一组k个元素
        return first;
    }
    /**
     * 指针移动反转单链表
     * @param head
     * @return
     */
    private static STLNode reverseSTL(STLNode head){
        STLNode pre = null;
        STLNode cur = head;
        while (cur != null){
            STLNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 递归实现单链表的反转
     * @param head
     * @return
     */
    private static STLNode recursiveReverseSTL(STLNode head){
        if (head == null || head.next == null){
            return head;
        }
        STLNode newHead = recursiveReverseSTL(head);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    /**
     * 链表的奇偶重排
     * 输入：1->2->3->4->5->null
     * 输出：1->3->5->2->4->null
     * @param head
     * @return
     */
    private STLNode oddEvenReArrange(STLNode head){
        STLNode odd = head;
        STLNode even = head.next;
        STLNode evenHead = even;
        while (even != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;//指向未尾的奇数

            even.next = odd.next;
            even =  even.next;//指向末尾的偶数
        }
        //最后的奇数指针指向偶数头部指针
        odd.next = evenHead;
        return head;
    }

    /**
     * 单链表的打印
     * @param head
     */
    private static void printSTL(STLNode head){
        while (head != null){
            System.out.println(TAG + ">>>>>>" + head.value);
            head = head.next;
        }
    }
}

